<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <p data-lake-id="u4032c1d7" id="u4032c1d7"><br></p>
  <h1 data-lake-id="GPotT" id="GPotT"><span data-lake-id="u3e86ef28" id="u3e86ef28">典型回答</span></h1>
  <p data-lake-id="u9e3c66a7" id="u9e3c66a7"><br></p>
  <p data-lake-id="u10f54c8c" id="u10f54c8c"><span data-lake-id="uc54efc19" id="uc54efc19">布隆过滤器是一种数据结构，用于快速检索一个元素是否可能存在于一个集合(bit 数组)中。</span></p>
  <p data-lake-id="u79e79c42" id="u79e79c42"><span data-lake-id="u9aa9ed00" id="u9aa9ed00">​</span><br></p>
  <p data-lake-id="u3fe35c94" id="u3fe35c94"><span data-lake-id="ua7e64396" id="ua7e64396">它的基本原理是利用多个哈希函数，将一个元素映射成多个位，然后将这些位设置为 1。当查询一个元素时，如果这些位都被设置为 1，则认为元素</span><strong><u><span data-lake-id="udbabffed" id="udbabffed">可能</span></u></strong><span data-lake-id="u9a5ca6ee" id="u9a5ca6ee">存在于集合中，否则</span><strong><u><span data-lake-id="uace21806" id="uace21806">肯定</span></u></strong><span data-lake-id="u713e05c8" id="u713e05c8">不存在。</span></p>
  <p data-lake-id="uaae50883" id="uaae50883"><span data-lake-id="u9a4a8087" id="u9a4a8087">​</span><br></p>
  <p data-lake-id="ud0268a56" id="ud0268a56"><span data-lake-id="ub779b0b4" id="ub779b0b4">所以，布隆过滤器可以准确的判断一个元素是否一定不存在，但是因为哈希冲突的存在，所以他没办法判断一个元素一定存在。只能判断可能存在。</span></p>
  <p data-lake-id="ud95a0ff5" id="ud95a0ff5"><span data-lake-id="uf303a77e" id="uf303a77e">​</span><br></p>
  <p data-lake-id="u56a3864b" id="u56a3864b"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1680881576213-a621153d-1d8c-412b-9234-de1766d018a5.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_40%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u0fe66745" id="u0fe66745"><br></p>
  <p data-lake-id="u7630f542" id="u7630f542"><span data-lake-id="u4bcf3dea" id="u4bcf3dea">所以，布隆过滤器是存在误判的可能的，也就是当一个不存在的Hero元素，经过hash1、hash2和hash3之后，刚好和其他的值的哈希结果冲突了。那么就会被误判为存在，但是其实他并不存在。</span></p>
  <p data-lake-id="u41ee8747" id="u41ee8747"><span data-lake-id="u659e437c" id="u659e437c">​</span><br></p>
  <p data-lake-id="ucc39d6fe" id="ucc39d6fe"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1680881991368-ad74c9de-fdef-4f7e-b4be-aad8364718e5.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_40%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u9f920f0b" id="u9f920f0b"><br></p>
  <p data-lake-id="uf2894708" id="uf2894708"><span data-lake-id="u2bbc5ebf" id="u2bbc5ebf">想要降低这种误判的概率，主要的办法就是降低哈希冲突的概率及引入更多的哈希算法。</span></p>
  <p data-lake-id="uf7653fed" id="uf7653fed"><span data-lake-id="u4540a18a" id="u4540a18a">​</span><br></p>
  <p data-lake-id="uc957582a" id="uc957582a"><span data-lake-id="u949e80ec" id="u949e80ec">下面是布隆过滤器的工作过程：</span></p>
  <p data-lake-id="ufc2f9487" id="ufc2f9487"><span data-lake-id="u2b79841f" id="u2b79841f">​</span><br></p>
  <ol list="ua59a9aff" data-lake-index-type="true">
   <li fid="ua274002b" data-lake-id="u0cdbb950" id="u0cdbb950"><span data-lake-id="u7cdc354c" id="u7cdc354c">初始化布隆过滤器</span></li>
  </ol>
  <p data-lake-id="u5b454dfb" id="u5b454dfb"><span data-lake-id="uc2279b6a" id="uc2279b6a">在初始化布隆过滤器时，需要指定集合的大小和误判率。布隆过滤器内部包含一个bit数组和多个哈希函数，每个哈希函数都会生成一个索引值。</span></p>
  <p data-lake-id="u0953d968" id="u0953d968"><span data-lake-id="udbb73e0e" id="udbb73e0e">​</span><br></p>
  <ol list="ua59a9aff" start="2" data-lake-index-type="true">
   <li fid="ua274002b" data-lake-id="u46f5bfa4" id="u46f5bfa4"><span data-lake-id="ub5c47ca0" id="ub5c47ca0">添加元素到布隆过滤器</span></li>
  </ol>
  <p data-lake-id="uc582b1cc" id="uc582b1cc"><span data-lake-id="uaeabf945" id="uaeabf945">要将一个元素添加到布隆过滤器中，首先需要将该元素通过多个哈希函数生成多个索引值，然后将这些索引值对应的位设置为 1。如果这些索引值已经被设置为 1，则不需要再次设置。</span></p>
  <p data-lake-id="u97547fa6" id="u97547fa6"><span data-lake-id="u6e83d59d" id="u6e83d59d">​</span><br></p>
  <ol list="ua59a9aff" start="3" data-lake-index-type="true">
   <li fid="ua274002b" data-lake-id="u0d6527bb" id="u0d6527bb"><span data-lake-id="u0fcc50c4" id="u0fcc50c4">查询元素是否存在于布隆过滤器中</span></li>
  </ol>
  <p data-lake-id="u6f84b5be" id="u6f84b5be"><span data-lake-id="ud45c8f6c" id="ud45c8f6c">要查询一个元素是否存在于布隆过滤器中，需要将该元素通过多个哈希函数生成多个索引值，并判断这些索引值对应的位是否都被设置为 1。如果这些位都被设置为 1，则认为元素可能存在于集合中，否则肯定不存在。</span></p>
  <p data-lake-id="uca41a6fe" id="uca41a6fe"><span data-lake-id="u33dff267" id="u33dff267">​</span><br></p>
  <p data-lake-id="ue997f955" id="ue997f955"><span data-lake-id="u59c1f6ab" id="u59c1f6ab">布隆过滤器的主要优点是可以快速判断一个元素是否属于某个集合，并且可以在空间和时间上实现较高的效率。但是，它也存在一些缺点，例如：</span></p>
  <p data-lake-id="u88882265" id="u88882265"><span data-lake-id="ub1a92a06" id="ub1a92a06">​</span><br></p>
  <ol list="u70a33126" data-lake-index-type="true">
   <li fid="u4f850cce" data-lake-id="uc66dc840" id="uc66dc840"><span data-lake-id="uad609d05" id="uad609d05">布隆过滤器在判断元素是否存在时，有一定的误判率。</span></li>
   <li fid="u4f850cce" data-lake-id="u52cd4ea8" id="u52cd4ea8"><span data-lake-id="u7d10f3fb" id="u7d10f3fb">布隆过滤器删除元素比较困难，因为删除一个元素需要将其对应的多个位设置为 0，但这些位可能被其他元素共享。</span></li>
  </ol>
  <p data-lake-id="uc33837a5" id="uc33837a5"><span data-lake-id="u59107e7d" id="u59107e7d">​</span><br></p>
  <h1 data-lake-id="p3ODh" id="p3ODh"><span data-lake-id="uef6b74cf" id="uef6b74cf">扩展知识</span></h1>
  <p data-lake-id="u1281b092" id="u1281b092"><br></p>
  <h2 data-lake-id="fPcqa" id="fPcqa"><span data-lake-id="u862601ba" id="u862601ba">应用场景</span></h2>
  <p data-lake-id="u5f070b20" id="u5f070b20"><br></p>
  <p data-lake-id="u38af8a57" id="u38af8a57"><span data-lake-id="u066f2482" id="u066f2482">布隆过滤器因为他的效率非常高，所以被广泛的使用，比较典型的场景有以下几个：</span></p>
  <p data-lake-id="u8a789cc0" id="u8a789cc0"><span data-lake-id="ua99bd558" id="ua99bd558">​</span><br></p>
  <ol list="ua88a3896" data-lake-index-type="true">
   <li fid="ub62cb1cc" data-lake-id="uc23d73b7" id="uc23d73b7"><span data-lake-id="ue55ff95c" id="ue55ff95c">网页爬虫：爬虫程序可以使用布隆过滤器来过滤掉已经爬取过的网页，避免重复爬取和浪费资源。</span></li>
   <li fid="ub62cb1cc" data-lake-id="u62d82d70" id="u62d82d70"><span data-lake-id="ufd9a4861" id="ufd9a4861">缓存系统：缓存系统可以使用布隆过滤器来判断一个查询是否可能存在于缓存中，从而减少查询缓存的次数，提高查询效率。布隆过滤器也经常用来解决缓存穿透的问题。</span></li>
   <li fid="ub62cb1cc" data-lake-id="ucd249be7" id="ucd249be7"><span data-lake-id="uad2cfd31" id="uad2cfd31">分布式系统：在分布式系统中，可以使用布隆过滤器来判断一个元素是否存在于分布式缓存中，避免在所有节点上进行查询，减少网络负载。</span></li>
   <li fid="ub62cb1cc" data-lake-id="ua99360cd" id="ua99360cd"><span data-lake-id="udefa9f8e" id="udefa9f8e">垃圾邮件过滤：布隆过滤器可以用于判断一个邮件地址是否在垃圾邮件列表中，从而过滤掉垃圾邮件。</span></li>
   <li fid="ub62cb1cc" data-lake-id="u8808a50b" id="u8808a50b"><span data-lake-id="u3d766097" id="u3d766097">黑名单过滤：布隆过滤器可以用于判断一个IP地址或手机号码是否在黑名单中，从而阻止恶意请求。</span></li>
  </ol>
  <p data-lake-id="u55a830e8" id="u55a830e8"><span data-lake-id="u140b02c0" id="u140b02c0">​</span><br></p>
  <p data-lake-id="u2e4fc78e" id="u2e4fc78e"><span data-lake-id="u3b0de86d" id="u3b0de86d">​</span><br></p>
  <h2 data-lake-id="XpGby" id="XpGby"><span data-lake-id="ua2c11229" id="ua2c11229">如何使用</span></h2>
  <p data-lake-id="ubdf5af9c" id="ubdf5af9c"><br></p>
  <p data-lake-id="uf4522025" id="uf4522025"><span data-lake-id="u860abf58" id="u860abf58">Java中可以使用第三方库来实现布隆过滤器，常见的有Google Guava库和Apache Commons库以及Redis。</span></p>
  <p data-lake-id="u961ae151" id="u961ae151"><span data-lake-id="ub7f2e29f" id="ub7f2e29f">​</span><br></p>
  <p data-lake-id="ud4b4aac6" id="ud4b4aac6"><span data-lake-id="ue38605d8" id="ue38605d8">如Guava：</span></p>
  <p data-lake-id="u6f67359b" id="u6f67359b"><span data-lake-id="u69c18a01" id="u69c18a01">​</span><br></p>
  <pre lang="java"><code>
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample {
    public static void main(String[] args) {
        // 创建布隆过滤器，预计插入100个元素，误判率为0.01
        BloomFilter&lt;String&gt; bloomFilter = BloomFilter.create(Funnels.stringFunnel(), 100, 0.01);

        // 插入元素
        bloomFilter.put("Hollis");
        bloomFilter.put("666");
        bloomFilter.put("八股文");

        // 判断元素是否存在
        System.out.println(bloomFilter.mightContain("Hollis")); // true
        System.out.println(bloomFilter.mightContain("王星星"));  // false
    }
}

</code></pre>
  <p data-lake-id="u4a7f6dc5" id="u4a7f6dc5"><br></p>
  <p data-lake-id="u468c0ca6" id="u468c0ca6"><br></p>
  <p data-lake-id="udf685288" id="udf685288"><span data-lake-id="u890013e1" id="u890013e1">Apache Commons：</span></p>
  <p data-lake-id="u17b9f9ad" id="u17b9f9ad"><span data-lake-id="u6377ddbf" id="u6377ddbf">​</span><br></p>
  <pre lang="java"><code>
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.collections4.BloomFilter;
import org.apache.commons.collections4.functors.HashFunctionIdentity;

public class BloomFilterExample {
    public static void main(String[] args) {
        // 创建布隆过滤器，预计插入100个元素，误判率为0.01
        BloomFilter&lt;String&gt; bloomFilter = new BloomFilter&lt;&gt;(HashFunctionIdentity.hashFunction(StringUtils::hashCode), 100, 0.01);

        bloomFilter.put("Hollis");
        bloomFilter.put("666");
        bloomFilter.put("八股文");

        // 判断元素是否存在
        System.out.println(bloomFilter.mightContain("Hollis")); // true
        System.out.println(bloomFilter.mightContain("王星星"));  // false
    }
}

</code></pre>
  <p data-lake-id="u69a53c97" id="u69a53c97"><br></p>
  <p data-lake-id="u6cce630c" id="u6cce630c"><br></p>
  <p data-lake-id="u5560d677" id="u5560d677"><span data-lake-id="u2c4e77ec" id="u2c4e77ec">Redis中可以通过Bloom模块来使用，使用Redisson可以：</span></p>
  <p data-lake-id="u0d15e42a" id="u0d15e42a"><br></p>
  <pre lang="java"><code>
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");

RedissonClient redisson = Redisson.create(config);
RBloomFilter&lt;String&gt; bloomFilter = redisson.getBloomFilter("myfilter");
bloomFilter.tryInit(100, 0.01);
bloomFilter.add("Hollis");
bloomFilter.add("666");
bloomFilter.add("八股文");
System.out.println(bloomFilter.contains("Hollis"));
System.out.println(bloomFilter.contains("王星星"));
redisson.shutdown();
</code></pre>
  <p data-lake-id="u8fea091b" id="u8fea091b"><br></p>
  <p data-lake-id="ub7813ce3" id="ub7813ce3"><br></p>
  <p data-lake-id="u47da8697" id="u47da8697"><span data-lake-id="uf9fc0f1e" id="uf9fc0f1e">首先创建一个RedissonClient对象，然后通过该对象获取一个RBloomFilter对象，使用tryInit方法来初始化布隆过滤器，</span><strong><span data-lake-id="u28569825" id="u28569825">指定了最多能添加的元素数量为100，误判率为0.01</span></strong><span data-lake-id="u4e50215b" id="u4e50215b">。然后，使用add方法将元素"Hollis"、"666"和"八股文"添加到布隆过滤器中，使用contains方法来检查元素是否存在于布隆过滤器中。</span></p>
  <p data-lake-id="uaa128c7e" id="uaa128c7e"><br></p>
  <p data-lake-id="uc81c5918" id="uc81c5918"><span data-lake-id="udc1bb558" id="udc1bb558">或者Jedis也可以：</span></p>
  <p data-lake-id="u5aaa5bfe" id="u5aaa5bfe"><span data-lake-id="u69a6d531" id="u69a6d531">​</span><br></p>
  <p data-lake-id="u000f4ef3" id="u000f4ef3"><span data-lake-id="u53be6b49" id="u53be6b49">​</span><br></p>
  <pre lang="java"><code>
Jedis jedis = new Jedis("localhost");
jedis.bfCreate("myfilter", 100, 0.01);
jedis.bfAdd("myfilter", "Hollis");
jedis.bfAdd("myfilter", "666");
jedis.bfAdd("myfilter", "八股文");
System.out.println(jedis.bfExists("myfilter", "Hollis"));
System.out.println(jedis.bfExists("myfilter", "王星星"));
jedis.close();

</code></pre>
 </body>
</html>